In general computer systems, a cache device is interposed between a main memory and a processor which reads information (data) from the main memory in order to reduce time to access the main memory.    [Patent Document 1]    Japanese Laid-open Patent Publication No. 7-152566
The cache device has a memory area (cache memory) where data can be written and read quicker, that is, access speed is faster than the main memory. The cache device stores contents (data) read from and written into locations in the main memory that have been accessed by the processor into the cache memory. When later on the processor accesses the similar data, the cache device retrieves the data from the cache memory, thereby apparently increasing the speed of access to the main memory.
Since data stored at multiple consecutive addresses are likely to be consecutively accessed, the cache device stores multiple blocks, each consisting of a predetermined amount (for example 32 bytes) of data in the cache memory. The cache device includes a management area where the storage locations (line numbers) of the blocks associated with addresses in the main memory are stored.
When requested data is found in the cache memory, it is called a cache hit; when requested data is not found in the cache memory, it is called a cache miss. When the processor requests access to data stored in the main memory, the conventional cache device compares the address of the data with the addresses stored in the management area to determine whether there is a cache hit or not. In the case of a cache hit, the cache device refers to the management area to find the line number of the block that contains the data and performs an operation responding to the access request on the block having the line number. For example, if the access request is a write request, the cache device stores the data output from the processor into the block; if the access request is a read request, the cache device outputs the data from the block to the processor. In the case of a cache miss, the cache device reads one block of data in the memory area that contains the requested data from the main memory, stores the block of data in the cache memory, and performs an operation for the access on the stored block of data.
Typical schemes for mapping a block in the main memory device to a block in the cache memory include set-associative, fully-associative, and sector mapping. Fully-associative mapping is better suited for random access compared with other mapping schemes and provides a higher cache hit ratio.
However, the cache device has latency, the time requested from access to be completed when a cache hit has occurred. Therefore, there is need for reducing time requested from access to be completed, that is, faster access speed.